/**
 * Jugs
 * Time Limit: 2 Seconds Memory Limit: 65536 KB Special Judge
 * In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted
 * with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug
 * and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem
 * generalizes that puzzle.
 * 
 * You have two jugs, A and B, and an infinite supply of water. There are three
 * types of actions that you can use: (1) you can fill a jug, (2) you can empty
 * a jug, and (3) you can pour from one jug to the other. Pouring from one jug
 * to the other stops when the first jug is empty or the second jug is full,
 * whichever comes first. For example, if A has 5 gallons and B has 6 gallons
 * and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in
 * A.
 * 
 * A problem is given by a triple (Ca,Cb,N), where Ca and Cb are the capacities
 * of the jugs A and B, respectively, and N is the goal. A solution is a
 * sequence of steps that leaves exactly N gallons in jug B. The possible steps
 * are
 * 
 * fill A
 * fill B
 * empty A
 * empty B
 * pour A B
 * pour B A
 * success
 * 
 * where "pour A B" means "pour the contents of jug A into jug B", and "success"
 * means that the goal has been accomplished.
 * 
 * You may assume that the input you are given does have a solution.
 * 
 * Input
 * 
 * Input to your program consists of a series of input lines each defining one
 * puzzle. Input for each puzzle is a single line of three positive integers:
 * Ca, Cb, and N. Ca and Cb are the capacities of jugs A and B, and N is the
 * goal. You can assume 0 < Ca <= Cb and N <= Cb <=1000 and that A and B are
 * relatively prime to one another.
 * 
 * Output
 * 
 * Output from your program will consist of a series of instructions from the
 * list of the potential output lines which will result in either of the jugs
 * containing exactly N gallons of water. The last line of output for each
 * puzzle should be the line "success". Output lines start in column 1 and there
 * should be no empty lines nor any trailing spaces.
 * 
 * Sample Input
 * 
 * 3 5 4
 * 5 7 3
 * 
 * Sample Output
 * 
 * fill B
 * pour B A
 * empty A
 * pour B A
 * fill B
 * pour B A
 * success
 * fill A
 * pour A B
 * fill A
 * pour A B
 * empty B
 * pour A B
 * success
 * 
 * 
 * 本题是Special Judge, 意思是不止一种答案。
 * 只要两个Jugs的容量是relatively-prime, 任何容量的结果都能实现。
 * 本题不用DFS, 有一种固定的解题方法。
 * 遍历方法为：
 * 
 * 循环开始
 * if(小桶空) then 倒满小桶 (fill 小桶)
 * 将小桶的水倒入大桶，直到小桶空或大桶满 (pour 小桶 大通)
 * if(大桶的水 == 所求的体积) then 跳出循环 (success)
 * if(大桶满了) then 清空大桶 (empty 大桶)
 * 
 * @author jasonleakey
 * 
 */
package edu.algorithm.acm.zoj1005;